/**
 * 二叉树节点定义
 */
export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

/**
 * 二叉树的层序遍历（广度优先搜索 BFS）
 * 按照从上到下、从左到右的顺序遍历每一层的节点
 * 
 * 算法思路：
 * 1. 使用队列（Queue）数据结构实现 BFS
 * 2. 将根节点入队
 * 3. 当队列不为空时：
 *    - 记录当前层的节点数量
 *    - 依次处理当前层的所有节点（出队、记录值、将子节点入队）
 *    - 将当前层的所有节点值添加到结果中
 * 4. 重复步骤3直到队列为空
 * 
 * 时间复杂度：O(n)，其中 n 是树中节点的数量
 * 空间复杂度：O(n)，最坏情况下队列需要存储最后一层的所有节点
 * 
 * @param root 二叉树的根节点
 * @returns 按层序遍历顺序返回的二维数组，每一层是一个子数组
 */
function levelOrder(root: TreeNode | null): number[][] {
    // 空树直接返回空数组
    if (!root) {
        return [];
    }
    
    // 使用队列存储待访问的节点，初始时将根节点入队
    const queue: TreeNode[] = [root];
    
    // 存储最终结果，每一层是一个子数组
    const res: number[][] = [];
    
    // 当队列不为空时，继续遍历
    while (queue.length) {
        // 记录当前层的节点数量（重要：需要在处理前记录，因为队列长度会变化）
        const levelSize = queue.length;
        
        // 存储当前层的所有节点值
        const level: number[] = [];
        
        // 遍历当前层的所有节点
        for (let i = 0; i < levelSize; i++) {
            // 从队列头部取出一个节点（FIFO：先进先出）
            const node = queue.shift()!;
            
            // 将当前节点的值添加到当前层的结果中
            level.push(node.val);
            
            // 如果左子节点存在，将其入队（下一层的节点）
            if (node.left) queue.push(node.left);
            
            // 如果右子节点存在，将其入队（下一层的节点）
            if (node.right) queue.push(node.right);
        }
        
        // 将当前层的所有节点值添加到最终结果中
        res.push(level);
    }
    
    // 返回按层序遍历的结果
    return res;
};
